package com.mdnote;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/11
 * @description
 */
public class MergeSortTemplate {

    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int begin, int end) {

        if (begin >= end) return;

        int mid = ((end - begin) >> 1) + begin;
        mergeSort(arr, begin, mid);
        mergeSort(arr, mid + 1, end);

        merge(arr, begin, mid, end);
    }

    private static void merge(int[] arr, int begin, int mid, int end) {
        int[] tmp = new int[end - begin + 1];

        // 一边比较一边放进去
        int i = begin, j =  mid + 1, k = 0;

        while (i <= mid && j <= end) {
            tmp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {tmp[k++] = arr[i++];}
        while (j <= end) {tmp[k++] = arr[j++];}

        for (int p = 0; p < tmp.length; p++) {
            arr[begin + p] = tmp[p];
        }
    }
}
